// 假设把某股票的价格按照时间先后顺序存储在数组中，
// 请问买卖该股票一次可能获得的最大利润是多少？

function maxProfit(prices: number[]): number {
  let dp: number = 0; // 当前天数卖出的最大利润
  let currMin: number = prices[0];// 截止至当前天的最小价格
  let maxProfit = 0;// 截止当前天的最大利润
  for (let num of prices) {
    currMin = Math.min(currMin, num);
    dp = num - currMin;
    maxProfit = Math.max(dp, maxProfit);// 状态转移方程
  }
  return maxProfit;
}

// 这道题目也是一个非常经典的的动态规划算法
// 首先定义状态变量dp，dp表示当前天卖出的最大利润
// 这里的条件转移方程也比较好理解，就是求解当前的dp
// 而当前的dp又等于当前的股票价格减去当前最便宜时刻买入的股票价格（currMin）
// 这里的dp变量可以降维处理，因为我们只需要知道当天的利润即可，
// 搭配我们维护的一个变量maxProfit，不断计算当前最大的利润
// 走完一遍数组返回即可。


